import java.util.Deque;
import java.util.LinkedList;

public class Test07 {
    /**
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
     * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
     * 方法一:
     * 1.如果根节点为空 , 返回空
     * 2.如果 p或者q 其中一个为根节点 ,则最近祖先为根节点,返回根节点
     * 3. p或者 q在根的左右两边
     *    p或者 q都在根的左边或者都在根的右边
     */
    public class TreeNode {
        public TreeNode left;
        public TreeNode right;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if (leftRet != null && rightRet != null) {//p 或者 q 在根节点左右两边
            return root;
        }else if (leftRet != null) {// p 或者 q 在根节点的左边
            return leftRet;
        }else if (rightRet != null) {//p 或者 q 在根节点的右边
            return rightRet;
        }
        return null;

    }

    /**
     * 方法二: 栈的方式
     * 找到从根节点到指定节点node 路径上的所有的节点,存放到栈当中
     * 1.两个栈当中存储好数据
     * 2.判断栈的大小
     * */
    public boolean getPath(TreeNode node,TreeNode root,Deque<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        //放入元素之后, 要检查
        if (root == node) {
            return true;
        }
        boolean ret1 = getPath(node,root.left,stack);
        if (ret1) return true;
        boolean ret2 = getPath(node,root.right,stack);
        if (ret2) return true;
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q) {
        //1.两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(p,root,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(q,root,stack2);
        //2.判断栈的大小
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
            int size = size1-size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        }else {
            int size = size2-size1;
            while (size !=0) {
                stack2.pop();
                size--;
            }
        }
        //栈里面数据个数是一样的
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }
}
